#include <iostream>
#include <stdio.h>

int main()
{
    int fib[100001] = {0, 1, 2};
    int f2 = 1, f1 = 2;
    int flag = 0;   // 记录第一个超过六位的斐波那契数是第几个斐波那契数
    for(int i = 3; i < 100001; ++i){
        fib[i] = (fib[i-1] + fib[i-2]);
        if(flag == 0 && fib[i] > 999999) flag = i;
        fib[i] %= 1000000;
    }
    int n;
    while(std::cin >> n){
        if(n >= flag)
            printf("%06d\n", fib[n]);
        else
            printf("%d\n", fib[n]);
    }
    return 0;
}